#include <iostream>
#include <string>
#include <ctime>
using namespace std;

string add(string augend, string addend);
string subtract(string minuend, string subtrahend);
string multiply(string multiplicand, string multiplier);
string divide(string dividend, string divisor);

void increaseZero(string& num, int size);//增加前导零，补充至len长度
void removeZero(string& num);//去除前导零
int numCompare(string num1, string num2);//两数字比较：大于返回1，等于返回0，小于返回-1

int main()
{
	int i, n;

	cout << "请输入大整数运算组数：";
	cin >> n;

	string** strNum = new string * [n];
	if (!strNum)
	{
		cout << "内存申请错误！！！" << endl;
		return 1;
	}
	for (i = 0; i < n; i++)
	{
		strNum[i] = new string[2];
		if (!strNum[i])
		{
			cout << "内存申请错误！！！" << endl;
			return 1;
		}
		cin >> strNum[i][0] >> strNum[i][1];
	}

	for (i = 0; i < n; i++)
	{
		clock_t start, end;
		cout << endl << "第" << i + 1 << "组数据运算结果为：" << endl;

		start = clock();
		cout << "\t相加：" << add(strNum[i][0], strNum[i][1]) << endl;
		end = clock();
		cout << "\t相加所用时间：" << end - start << "毫秒" << endl << endl;

		start = clock();
		cout << "\t相减：" << subtract(strNum[i][0], strNum[i][1]) << endl;
		end = clock();
		cout << "\t相减所用时间：" << end - start << "毫秒" << endl << endl;

		start = clock();
		cout << "\t相乘：" << multiply(strNum[i][0], strNum[i][1]) << endl;
		end = clock();
		cout << "\t相乘所用时间：" << end - start << "毫秒" << endl << endl;

		start = clock();
		string quotient = divide(strNum[i][0], strNum[i][1]);
		end = clock();
		if (quotient == "ERROR")
		{
			cout << "\t除数不能为0！！！" << endl;
		}
		else
		{
			cout << "\t相除：" << quotient << endl;
		}
		cout << "\t相除所用时间：" << end - start << "毫秒" << endl;
	}

	for (i = 0; i < n; i++)
	{
		delete[] strNum[i];
	}
	delete[] strNum;

	system("pause");
	return 0;
}

string add(string augend, string addend)
{
	//其实新版小学教材不再区分被加数与加数，统称加数
	string sum;

	if (augend[0] == '-' && addend[0] == '-')//两负数相加等于两数的绝对值相加，再在和前加负号
	{
		sum = add(augend.erase(0, 1), addend.erase(0, 1));
		sum.insert(sum.begin(), '-');
	}
	else if (augend[0] == '-' && addend[0] != '-')//一负一正相加等于正数减负数的绝对值
	{
		sum = subtract(addend, augend.erase(0, 1));
	}
	else if (augend[0] != '-' && addend[0] == '-')//一正一负相加等于正数减负数的绝对值
	{
		sum = subtract(augend, addend.erase(0, 1));
	}
	else//两正数相加
	{
		//按两数位数最大者补位
		if (augend.size() > addend.size())
		{
			increaseZero(addend, augend.size());
		}
		else if (augend.size() < addend.size())
		{
			increaseZero(augend, addend.size());
		}

		int flg = 0;//进位标志
		for (int i = augend.size() - 1; i >= 0; i--)
		{
			//ASCII码数字相加
			sum.insert(sum.begin(), augend[i] + addend[i] + flg - '0');

			flg = (sum[0] - '0') / 10;
			if (sum[0] > '9')
			{
				sum[0] = (sum[0] - '0') % 10 + '0';
			}
		}
		//最高位相加如果进位标志等于1，和前补1
		if (flg)
		{
			sum.insert(sum.begin(), '1');
		}
	}
	return sum;
}

string subtract(string minuend, string subtrahend)
{
	string difference;

	if (minuend[0] == '-' && subtrahend[0] == '-')//两负数相减等于减数的绝对值减被减数的绝对值
	{
		difference = subtract(subtrahend.erase(0, 1), minuend.erase(0, 1));
	}
	else if (minuend[0] == '-' && subtrahend[0] != '-')//一负一正相减等于正数加负数的绝对值，再在和前加负号
	{
		difference = add(minuend.erase(0, 1), subtrahend);
		difference.insert(difference.begin(), '-');
	}
	else if (minuend[0] != '-' && subtrahend[0] == '-')//一正一负相减等于正数加负数的绝对值的和
	{
		difference = add(minuend, subtrahend.erase(0, 1));
	}
	else//两正数相减
	{
		int flag = numCompare(minuend, subtrahend);
		if (flag == -1)//小数减大数
		{
			difference = subtract(subtrahend, minuend);
			difference.insert(difference.begin(), '-');
		}
		else if (flag == 0)//相同数相减
		{
			difference.assign("0");
		}
		else//大数减小数
		{
			if (minuend.size() > subtrahend.size())
			{
				increaseZero(subtrahend, minuend.size());
			}

			int flg = false;//借位标志
			for (int i = minuend.size() - 1; i >= 0; i--)
			{
				//ASCII码数字相减
				difference.insert(difference.begin(), minuend[i] - subtrahend[i] - flg + '0');

				if (difference[0] < '0')
				{
					difference[0] += 10;
					flg = 1;
				}
				else
				{
					flg = 0;
				}
			}
			removeZero(difference);
		}
	}
	return difference;
}

string multiply(string multiplicand, string multiplier)
{
	string product;

	if (multiplicand[0] == '-' && multiplier[0] == '-')//两负数相乘等于两数的绝对值相乘
	{
		product = multiply(multiplicand.erase(0, 1), multiplier.erase(0, 1));
	}
	else if (multiplicand[0] == '-' && multiplier[0] != '-')//一负一正相乘于正数乘负数的绝对值，再在积前加负号
	{
		product = multiply(multiplicand.erase(0, 1), multiplier);
		product.insert(product.begin(), '-');
	}
	else if (multiplicand[0] != '-' && multiplier[0] == '-')//一正一负相乘于正数乘负数的绝对值，再在积前加负号
	{
		product = multiply(multiplicand, multiplier.erase(0, 1));
		product.insert(product.begin(), '-');
	}
	else//两正数相乘
	{
		//手工乘法模拟
		int i;
		string* tmp = new string[multiplier.size()];
		for (i = multiplier.size() - 1; i >= 0; i--)
		{
			int j;
			string* temp = new string[multiplicand.size()];
			for (j = multiplicand.size() - 1; j >= 0; j--)
			{
				int pro = (multiplier[i] - '0') * (multiplicand[j] - '0');
				if (!pro)
				{
					temp[j].assign("0");
				}
				else
				{
					while (pro != 0)
					{
						temp[j].insert(temp[j].begin(), pro % 10 + '0');
						pro /= 10;
					}
				}
			}

			tmp[i] = "0";
			for (j = multiplicand.size() - 1; j >= 0; j--)
			{
				if (temp[j] == "0")
				{
					continue;
				}
				for (int k = 1; k <= multiplicand.size() - j - 1; k++)
				{
					temp[j].push_back('0');
				}
				tmp[i] = add(tmp[i], temp[j]);
			}
			delete[] temp;
		}

		product = "0";
		for (i = multiplier.size() - 1; i >= 0; i--)
		{
			if (tmp[i] == "0")
			{
				continue;
			}
			for (int j = 1; j <= multiplier.size() - i - 1; j++)
			{
				tmp[i].push_back('0');
			}
			product = add(product, tmp[i]);
		}
		delete[] tmp;
	}
	return product;
}

string divide(string dividend, string divisor)
{
	string quotient;

	if (divisor == "0")
	{
		quotient.assign("ERROR");
	}
	else
	{
		if (dividend[0] == '-' && divisor[0] == '-')//两负数相除等于两数的绝对值相除
		{
			quotient = divide(dividend.erase(0, 1), divisor.erase(0, 1));
		}
		else if (dividend[0] == '-' && divisor[0] != '-')//一负一正相除等于被除数的绝对值除以除数，再在商前加负号
		{
			quotient = divide(dividend.erase(0, 1), divisor);
			quotient.insert(quotient.begin(), '-');
		}
		else if (dividend[0] != '-' && divisor[0] == '-')
		{
			quotient = divide(dividend, divisor.erase(0, 1));//一正一负相除等于被除数除以除数的绝对值，再在商前加负号
			quotient.insert(quotient.begin(), '-');
		}
		else//两正数相除
		{
			int flag = numCompare(dividend, divisor);
			if (flag == -1)//小数除大数
			{
				quotient.assign("0");
			}
			else if (flag == 0)//相同数相除
			{
				quotient.assign("1");
			}
			else//大数除小数
			{
				quotient = "0";
				while (numCompare(dividend, divisor) != -1)
				{
					dividend = subtract(dividend, divisor);
					quotient = add(quotient, "1");
				}
			}
		}
	}
	return quotient;
}

void increaseZero(string& num, int len)
{
	int tmp = len - num.size();
	for (int i = 1; i <= tmp; i++)
	{
		num.insert(num.begin(), '0');
	}
}

void removeZero(string& num)
{
	while (num[0] == '0')
	{
		num.erase(0, 1);
	}

	if (num.empty())
	{
		num.assign("0");
	}
}

int numCompare(string num1, string num2)
{
	if (num1.size() > num2.size())
	{
		return 1;
	}
	else if (num1.size() == num2.size())
	{
		int i;
		for (i = 0; i < num1.size(); i++)
		{
			if (num1[i] > num2[i])
			{
				return  1;
			}
			else if (num1[i] < num2[i])
			{
				return -1;
			}
		}
		return 0;
		/*
		if (i == num1.size())
		{
			return 0;
		}
		*/
	}
	else
	{
		return -1;
	}
}